Field of the Invention
The invention relates to apparatus for quickly sorting a succession of data words on the basis of the value of a specific parameter associated with each data word.
Description of the Prior Art
In certain fields of use the word metric is associated with the parameter value. In a general sense two kinds of sorting apparatus can be distinguished. The first kind sorts a very large number of data words which concern, for example, changes to be carried out in bank accounts. These words have to be sorted, for example, according to successive account numbers (=parameters). The number of possible parameters is very large in such cases and it is impossible to execute the sorting operation in real time when the data words are supplied by an electronic feed mechanism. Extensive buffering is therefore required, the two data files ultimately being combined. This kind of apparatus therefore performs off-line batch processing of a data file.
A second kind of sorting apparatus cooperates in real time with the data input, but there is a penalty in that only a limited number of parameter values are permissible. The parameters may be, for example, measurement values from a corresponding number of measuring elements, each associated data word indicating the identity of the measuring element. The value of the parameter may alternatively represent a quality property of the data word, each data word being a possibility which is permissible a priori; the apparatus may then serve to select the best possibility from a limited number of possibilities and/or to select a number of the best possibilities in order to obtain ultimately the best choice. In this last case the problem in its most general form is to estimate the maximum a posteriori probability of the state sequence of a finite-state discrete-time Markov process observed in memoryless noise. According to the literature, this can be done by means of the Viterbi algorithm; a tutorial exposition of this has been published by G. David Forney, jr. in Proceedings of the IEEE, Vol. 61, No. 3, March 1973, pages 268-278. Applications lie in the fields of problems as regards error-correcting convolutional codes, intersymbol interference, continuous-phase frequency shift keying (FSK), and text recognition. Each data word represents a "path" in a "grid" or "trellis" according to Viterbi, said path having a starting point and an end point. A path consists of a number of segments, a partial parameter being assigned to each segment. The sum of the partial parameters of a path represents the parameter of said path, and the object is to establish the path having the lowest (or the highest) parameter. In principle, a path continues with the incoming data stream, thus its end is continuously shifted so that continuously new segments have to be taken into account. The paths continuously diverge and converge again; in the case of convergence, only the parameter of one of the converging paths is further taken into account. A particular application of the Viterbi algorithm for processing a data stream embodying an error correcting code, which application utilizes a maximum likelihood decoder, is described in: A. J. Vinck et al., "A Class of Binary Rate one-half Convolutional Codes that Allow an Improved Stack Decoder", IEEE Trans. on Information Theory, IT 26 (July 1980) p. 389 ff.